package leetcode

import com.sun.org.apache.bcel.internal.generic.IFEQ
import kotlinetc.println

//https://leetcode.com/problems/concatenated-words/

/**
Given a list of words (without duplicates), please write a program that returns all concatenated words in the given list of words.
A concatenated word is defined as a string that is comprised entirely of at least two shorter words in the given sort.getArray.

Example:
Input: ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]

Output: ["catsdogcats","dogcatsdog","ratcatdogcat"]

Explanation: "catsdogcats" can be concatenated by "cats", "dog" and "cats";
"dogcatsdog" can be concatenated by "dog", "cats" and "dog";
"ratcatdogcat" can be concatenated by "rat", "cat", "dog" and "cat".
Note:
The number of elements of the given sort.getArray will not exceed 10,000
The length sum of elements in the given sort.getArray will not exceed 600,000.
All the input string will only include lower case letters.
The returned elements order does not matter.
 */
fun main(args: Array<String>) {
    //""   ""
    findAllConcatenatedWordsInADict(
            arrayOf("")
    ).size.println()
}

/**
 * 其实就是[wordBreak]的反例，wordbreak是给定单词和词典，看单词是否可以由词典中的词构成
 *
 * 而这题可以认为是把单词和词典混合在一起，那么对当前单词来说，除去当前单词的剩余单词作为词典
 *
 * 也可以考虑用字典树Trie
 */
fun findAllConcatenatedWordsInADict(words: Array<String>): List<String> {

    val result = arrayListOf<String>()
    val wordsSet = words.toHashSet()
    words.forEachIndexed { index, word ->
        wordsSet.remove(word)

        val dp = Array(word.length + 1) { false }
        dp[0] = true

        for (i in 1 until word.length + 1) {
            for (j in 0 until i + 1) {
                if (dp[j] && wordsSet.contains(word.substring(j, i))) {
                    dp[i] = true
                    break
                }
            }
        }

        if (dp.last() && word.isNotEmpty())
            result.add(word)
        wordsSet.add(word)

    }

    return result
}